#
# @lc app=leetcode.cn id=239 lang=python3
#
# [239] 滑动窗口最大值
#

# @lc code=start

from typing import List
from collections import deque

class Solution:
    
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        result = []
        self.q = deque()
        self.windowsSize = k
        if len(nums) == 0:
            return result
        
        if len(nums) < self.windowsSize:
            for index in range(0, len(nums)):
                self.addValueToWindow(index, value)
            return self.q[0][1]
        
        for i in range(0, self.windowsSize - 1):
            self.addValueToWindow(i, nums[i])
            
        for i in range(self.windowsSize - 1, len(nums)):
            self.addValueToWindow(i, nums[i])
            result.append(self.q[0][1])
        return result
    
    def addValueToWindow(self, index, value):
        while len(self.q) > 0 and (value > self.q[-1][1]):
            self.q.pop()
        self.q.append((index, value))
        if self.q[0][0] + self.windowsSize == index:
            self.q.popleft()
        
# @lc code=end

